When writing computer programs it is sometimes the case that errors, or ‘bugs’, are included in a program. Sometimes this is due to typographical errors in writing the source code (e.g. omitting a character or substituting one character for another), sometimes due to implementing incorrect functionality (e.g. causing a loop to terminate at one when it ought to terminate at zero) and sometimes due to errors in other programs upon which the author is relying, for example a library routine or even the compiler itself.
A debugger can help someone attempting to find and remove bugs from a program. Prior art debuggers have tended to focus upon inserting so-called breakpoints into a program and running a program forwards in time, stopping at one or more of the breakpoints in order to examine the state of the program (content of processor registers, content of memory) at that breakpoint in the hope of catching an error before it causes the program to crash. Crashing can take many forms, generally summarised as the program not running as intended, for example a segmentation fault, an unhandled exception or an infinite loop (where a program stops responding to user input and executes the same routines indefinitely). An example of such a prior art debugger is GDB, the GNU Project Debugger.
However, the cause of an error in a program may occur long before the error manifests itself. This makes such forward debugging difficult, as it may not be obvious which particular change in program state caused an error, especially if it occurred a long time previous to the error actually showing up, with many correct program operations in the intermediate period. Furthermore, some errors are more easy to spot than others, as in general a computer simply does what it is programmed to do, and the cause of the error may lie in the user's understanding of how it works, as distinct from how it actually works. On the other hand, a user may have a correct understanding of how his program is intended to work, but if there are errors in a library routine upon which he is relying (for example a mathematical square root function), then the program may give the wrong result even though the parts of the program written by the user are functioning as the user intended. In this case there are two options for correcting the error; the first is to correct the error in the library routine (which may not always be possible as a user may not always have access to the source code of library routines) and the second is to provide a ‘workaround’ in the user's program to ensure that the error in the library routine does not cause his own program to give the wrong results.
For these reasons and others it would be useful to be able to step backwards in the execution of a computer program so as to be able to trace an error from the moment it caused the program to crash back until the error first appeared. This is impossible with conventional prior art debuggers as these only allow forward execution of programs. Backwards execution is actually a hard problem to solve, as in the process of executing a program there may be intermediate results which are lost as the program executes, making it difficult to return to a previous state unless a record is kept of these results. Furthermore, due to the operation of jump instructions in a program, it can impossible to tell, without keeping a record of program execution, where execution was taking place in a program prior to the current position. It could have been executing the instruction before the current one, or it could have just executed a jump instruction somewhere else which caused execution to jump to the current position. In addition, with variable length instruction sets such as Intel IA32 it may not be possible to trace execution backwards at all without keeping some kind of record, since there may be no way of knowing whether the previous instruction was a one byte instruction just before the current position, or a two byte instruction two places before the current position, and so on.
Several attempts have been made to solve the problem of backwards debugging, but a solution to the problem of non-determinism in programs has remained elusive. One approach to the problem of backwards debugging is described in the paper “Efficient Algorithms for Bidirectional Debugging” (Boothe, 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation, Vancouver, British Columbia). This describes a source code C and C++ debugger running on Digital/Compaq Alpha based UNIX workstations. This debugger describes embedding event counters into the program being debugged and using these counters to identify a target event on the fly as the target program executes.
However there are a number of problems with this approach. Firstly, it fails to properly address the problem of non-determinism. Secondly, as it operates on the source code of a program not the object code, if a problem occurs with a program for which the source code is not available, it will not be possible to debug the program using this method. Thirdly the bug that is being hunted is likely to cause the backwards debugger itself to malfunction. Fourthly the approach cannot be used on bugs which cause the program to function outside the normal control flow implied by the source language (for example, returning from a function after the stack has been corrupted). Fifth, if a problem occurs due to the functioning of the compiler itself, it may not be possible to detect the problem as the program is not compiled in its ‘normal’ form at all—instead a modified version of the program including debug routines is compiled, in which the problem with the compiler may not manifest itself, or may manifest itself in a completely different way. Sixth, different debugger programs would have to be written for debugging source code written in different programming languages, and it does not provide a solution at all for the problem of debugging programs written in machine code.
It would be advantageous to provide a debugger capable of backwards debugging which addresses the above-cited problems.